/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-05-25 15:12:08
 * @LastEditors: lily
 * @LastEditTime: 2021-05-25 16:58:13
 */
/*
 * @lc app=leetcode.cn id=73 lang=javascript
 *
 * [73] 矩阵置零
 */

// @lc code=start
/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
//  思想：
//  找出数组中的0，再对数组进行操作
//  自做用两个数组保存了出现0的行数/列数 空间复杂度O(m + n)
//  可以用原数组的首行、首列代替上述数组，并用两个变量维持首行、首列是否含有0，将空间复杂度降至 O(1)

//  复杂度： O(mn) O(1)

var setZeroes = function (matrix) {
    const rl = matrix.length, cl = matrix[0].length
    let rowFlag = false, colFlag = false
    // 设置标记
    for (let j = 0; j < cl; j++) {
        // !0 ==> xxx === 0
        if (!matrix[0][j]) {
            rowFlag = true
        }
    }
    for (let i = 0; i < rl; i++) {
        if (!matrix[i][0]) {
            colFlag = true
        }
    }
    for (let i = 1; i < rl; i++) {
        for (let j = 1; j < cl; j++) {
            if (!matrix[i][j]) {
                matrix[i][0] = matrix[0][j] = 0
            }
        }
    }

    // 根据标记置零
    for (let i = 1; i < rl; i++) {
        for (let j = 1; j < cl; j++) {
            if (!matrix[i][0] || !matrix[0][j]) {
                matrix[i][j] = 0
            }
        }
    }
    if (rowFlag) {
        for (let j = 0; j < cl; j++) {
            matrix[0][j] = 0
        }
    }
    if (colFlag) {
        for (let i = 0; i < rl; i++) {
            matrix[i][0] = 0
        }
    }
};
// @lc code=end

var setZeroes1 = function (matrix) {
    const rl = matrix.length, cl = matrix[0].length
    let row = [], col = []
    for (let i = 0; i < rl; i++) {
        for (let j = 0; j < cl; j++) {
            if (matrix[i][j] === 0) {
                row.push(i)
                col.push(j)
            }
        }
    }
    for (const i of row) {
        for (let j = 0; j < cl; j++) {
            matrix[i][j] = 0
        }
    }
    for (const j of col) {
        for (let i = 0; i < rl; i++) {
            matrix[i][j] = 0
        }
    }
};

let matrix = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
setZeroes(matrix)
console.log(matrix);